#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define Status int
#define ElemType int

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;

//1.线性表的合并
//  	 问题描述：假设利用两个线性表La,Lb分别表示两个集合A,B，现要求一个新的集合 A = A ∪B 
//					La = (7,5,3,11)  Lb = (2,6,3)  ====>  La = (7,5,3,11,2,6)

LNode *MergeList(LinkList La, LinkList Lb)
{
	LNode *r = La;
	while(r->next){
		r = r->next;	//找到La的尾结点 
	}
	LNode *p = Lb;
	while(p->next){
		p = p->next;
		LNode *q = La->next;
		while(q->data != p->data && q->next){
			q = q->next;
		}
		if(q->data != p->data){
			LNode *s = new LNode;
			s->data = p->data;
			s->next = NULL;
			r->next = s;
			r = s;
		}

	}
	return La;
}
//伪码如下： 
//void union(LinkList &La, LinkList Lb){
//	int La_len = ListLength(La);
//	int Lb_len = Listlength(Lb);
//	for(int i = 1; i < Lb_len; i++){
//		GetElem(Lb, i , e);
//		if(!LocateElem(La, e)) ListInesrt(&La, ++La_len, e);
//	} 
//} 


//尾插法创建单链表
void CreateList_R(LinkList &L, int length){
	L = new LNode;
	L->next = NULL;
	LNode *p = L;
	for(int i = 1; i <= length; i++){
		LNode *s = new LNode;
		printf("请输入第%d个结点的数据：", i);
		cin>>s->data;
		p->next = s;
		s->next = NULL;
		p = s;
	}
	printf("创建完成!\n");
} 
void DisputeList(LinkList L){
	LNode *q = L;
	while(q->next){
		q = q->next;
		printf("%d ", q->data);
	}
	puts("");
}


int ListLength(LinkList La){
	LNode *p = La;
	int length = 0;
	while(p->next){
		length++;
		p = p->next;
	}
	return length;
}


//2.有序表的合并
//		问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列
//				  La = (1,7,8)  Lb = (2,4,6,8,10,11)  ===>  Lc = (1,2,4,6,7,8,8,10,11) 

LNode *MergeSortedList(LinkList La, LinkList Lb, LinkList &Lc){
	Lc = new LNode;
	Lc = La; //用La的头结点作为Lc的头结点 
	LNode *pa = La->next;
	LNode *pb = Lb->next;
	LNode *pc =Lc;  
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pa = pa->next;
			pc = pc->next;
		}else{
			pc->next = pb;
			pb = pb->next;
			pc = pc->next;
		}
	}
	pc->next = pa? pa : pb; //插入剩余段 
	//delete(Lb); //释放Lb头结点 
	return Lc;
}



int main(void)
{
	LinkList La, Lb;
	int length_la,length_lb;
	printf("请输入链表La的长度：");
	cin>>length_la; 
	CreateList_R(La, length_la);
	printf("La：");
	DisputeList(La);
	printf("请输入链表Lb的长度：");
	cin>>length_lb;
	CreateList_R(Lb, length_lb);
	printf("Lb: ");
	DisputeList(Lb);
	printf("---------------------------\n");
	printf("两表合并为Lc：");
	LinkList Lc;
	Lc = MergeSortedList(La, Lb, Lc);
	DisputeList(Lc);
	printf("---------------------------\n");
	La = MergeList(La, Lb);
	puts("La,Lb合并为La：");
	DisputeList(La);	
	return 0;			
} 